class node():
    def __init__(self,p=None,key=None,left=None,right=None,color=None,size=1,m=0):
        self.key=key
        self.p=p
        self.left=left
        self.right=right
        self.color=color
        self.size = size
        self.m = m
        if self.key=='NIL':
            self.color='black'
            self.left=self
            self.right=self
            self.size = 0
    def __repr__(self):
        if self.color=='red':
            return str(self.key)+'R'
        if self.color=='black':
            return str(self.key)+'B'
        return str(self.key)
    def inorder(self,NIL):
        if self.left is not NIL:
            self.left.inorder(NIL)
        print self, 
        if self.right is not NIL:
            self.right.inorder(NIL)
    def search(self,k,NIL):
        if k==self.key:
            return self
        elif k<self.key:
            if self.left is NIL:
                return NIL
            else:
                return self.left.search(k,NIL)
        else:
            if self.right is NIL:
                return NIL
            else:
                return self.right.search(k,NIL)
    def minimum(self,NIL):
        x=self
        while x.left is not NIL:
            x=x.left
        return x
    def successor(self,NIL):
        if self.right is not NIL:
            return self.right.minimum(NIL)
        x=self
        while x.p is not NIL and x.p.right is x:
            x=x.p
        return x.p
    def os_select(self, i):
        r = self.left.size + 1
        if i == r: return self.key
        elif i < r:
            return self.left.os_select(i)
        else:
            return self.right.os_select(i - r)
    def os_key_rank(self, k):
        if self.key == 'NIL': return 'not found'
        if self.key == k: return self.left.size + 1
        elif k < self.key:
            return self.left.os_key_rank(k)
        else:
            ret = self.right.os_key_rank(k)
            if ret == 'not found': return ret
            else: return self.left.size + 1 + ret

class BST():
    def __init__(self):
        self.root=None
    def inorder(self,NIL):
        if self.root is not NIL:
            self.root.inorder(NIL)
            print
        else:
            print 'empty BST'
    def search(self,k,NIL):
        if self.root is NIL:
            return NIL
        else:
            return self.root.search(k,NIL)
    def search_iterative(self,k,NIL):
        x=self.root
        while x is not NIL and x.key!=k:
            if k<x.key:
                x=x.left
            else:
                x=x.right
        return x


